Computer Science Engineering (CSE) Exam  >  Computer Science Engineering (CSE) Questions  >  Consider a weighted complete graph G on the v... Start Learning for Free
Consider a weighted complete graph G on the vertex set {v1, v2, .... vn} such that the weight of the edge (vi, vj) is 2 | i - j | .The weight of a minimum 
  • a)
    n-1
  • b)
    2n-2
  • c)
    n/2
  • d)
    n2
Correct answer is option 'B'. Can you explain this answer?
Verified Answer
Consider a weighted complete graph G on the vertex set {v1, v2, .... v...
In the case of minimum spanning tree of a graph G we will add up to ( n - 1) vertices, so the weight of a minimum spanning tree of G
View all questions of this test
Most Upvoted Answer
Consider a weighted complete graph G on the vertex set {v1, v2, .... v...
Weighted Complete Graph:
A weighted complete graph is a graph where every pair of vertices is connected by an edge, and each edge has a weight assigned to it.

Weight of Edges:
In this graph, the weight of the edge (vi, vj) is given by the formula 2 | i - j |, where i and j are the indices of the vertices.

Minimum Weight:
We need to find the weight of a minimum spanning tree (MST) in this graph. An MST is a tree that connects all the vertices in the graph with the minimum total weight.

Algorithm:
To find the weight of the MST in this graph, we can use Kruskal's algorithm or Prim's algorithm.

Kruskal's Algorithm:
1. Sort all the edges in non-decreasing order of their weights.
2. Initialize an empty set of edges, which will form the MST.
3. Iterate over the sorted edges and add each edge to the MST set if it doesn't form a cycle.
4. Stop when there are n-1 edges in the MST set, where n is the number of vertices in the graph.

Explanation:
In this graph, there are n vertices labeled v1, v2, ..., vn. Since it is a complete graph, there will be n*(n-1)/2 edges.

The weight of an edge (vi, vj) is given by 2 | i - j |. Let's consider two cases:

1. When i < />
- The weight of the edge (vi, vj) is 2(j - i).
- For any vertex vi, there are (n - i) vertices with indices greater than i.
- So, the total weight contributed by vertex vi in the MST is 2(j - i) * (n - i).

2. When i > j:
- The weight of the edge (vi, vj) is 2(i - j).
- For any vertex vi, there are (i - 1) vertices with indices smaller than i.
- So, the total weight contributed by vertex vi in the MST is 2(i - j) * (i - 1).

Weight of MST:
To find the weight of the MST, we need to sum up the contributions from each vertex:
Weight of MST = Σ [2(j - i) * (n - i)] + Σ [2(i - j) * (i - 1)]

Simplification:
By simplifying the above expressions, we can show that the weight of the MST is 2(n-1)(n-2).

Conclusion:
The weight of the MST in this graph is 2(n-1)(n-2), which is equivalent to 2n-2. Therefore, the correct answer is option 'B'.
Explore Courses for Computer Science Engineering (CSE) exam

Top Courses for Computer Science Engineering (CSE)

Question Description
Consider a weighted complete graph G on the vertex set {v1, v2, .... vn} such that the weight ofthe edge (vi, vj) is 2 | i - j |.The weight of a minimuma)n-1b)2n-2c)n/2d)n2Correct answer is option 'B'. Can you explain this answer? for Computer Science Engineering (CSE) 2025 is part of Computer Science Engineering (CSE) preparation. The Question and answers have been prepared according to the Computer Science Engineering (CSE) exam syllabus. Information about Consider a weighted complete graph G on the vertex set {v1, v2, .... vn} such that the weight ofthe edge (vi, vj) is 2 | i - j |.The weight of a minimuma)n-1b)2n-2c)n/2d)n2Correct answer is option 'B'. Can you explain this answer? covers all topics & solutions for Computer Science Engineering (CSE) 2025 Exam. Find important definitions, questions, meanings, examples, exercises and tests below for Consider a weighted complete graph G on the vertex set {v1, v2, .... vn} such that the weight ofthe edge (vi, vj) is 2 | i - j |.The weight of a minimuma)n-1b)2n-2c)n/2d)n2Correct answer is option 'B'. Can you explain this answer?.
Solutions for Consider a weighted complete graph G on the vertex set {v1, v2, .... vn} such that the weight ofthe edge (vi, vj) is 2 | i - j |.The weight of a minimuma)n-1b)2n-2c)n/2d)n2Correct answer is option 'B'. Can you explain this answer? in English & in Hindi are available as part of our courses for Computer Science Engineering (CSE). Download more important topics, notes, lectures and mock test series for Computer Science Engineering (CSE) Exam by signing up for free.
Here you can find the meaning of Consider a weighted complete graph G on the vertex set {v1, v2, .... vn} such that the weight ofthe edge (vi, vj) is 2 | i - j |.The weight of a minimuma)n-1b)2n-2c)n/2d)n2Correct answer is option 'B'. Can you explain this answer? defined & explained in the simplest way possible. Besides giving the explanation of Consider a weighted complete graph G on the vertex set {v1, v2, .... vn} such that the weight ofthe edge (vi, vj) is 2 | i - j |.The weight of a minimuma)n-1b)2n-2c)n/2d)n2Correct answer is option 'B'. Can you explain this answer?, a detailed solution for Consider a weighted complete graph G on the vertex set {v1, v2, .... vn} such that the weight ofthe edge (vi, vj) is 2 | i - j |.The weight of a minimuma)n-1b)2n-2c)n/2d)n2Correct answer is option 'B'. Can you explain this answer? has been provided alongside types of Consider a weighted complete graph G on the vertex set {v1, v2, .... vn} such that the weight ofthe edge (vi, vj) is 2 | i - j |.The weight of a minimuma)n-1b)2n-2c)n/2d)n2Correct answer is option 'B'. Can you explain this answer? theory, EduRev gives you an ample number of questions to practice Consider a weighted complete graph G on the vertex set {v1, v2, .... vn} such that the weight ofthe edge (vi, vj) is 2 | i - j |.The weight of a minimuma)n-1b)2n-2c)n/2d)n2Correct answer is option 'B'. Can you explain this answer? tests, examples and also practice Computer Science Engineering (CSE) tests.
Explore Courses for Computer Science Engineering (CSE) exam

Top Courses for Computer Science Engineering (CSE)

Explore Courses
Signup for Free!
Signup to see your scores go up within 7 days! Learn & Practice with 1000+ FREE Notes, Videos & Tests.
10M+ students study on EduRev